package club.xiaojiawei.binarytree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/11/22 12:27 AM
 * @question 515. 在每个树行中找最大值
 * @description 给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
 */
public class LargestValues515 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(3);
        TreeNode right = new TreeNode(2);
        left.left = new TreeNode(5);
        left.right = new TreeNode(3);
        right.right = new TreeNode(9);
        root.left = left;
        root.right = right;
        List<Integer> result = largestValues(root);
        System.out.println(result);
    }

    /**
     * DFS+递归
     * @param root
     * @return
     */
    public static List<Integer> largestValues(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        max(root, 0, result);
        return result;
    }

    public static void max(TreeNode node, int depth, List<Integer> list){
        if (node == null){
            return;
        }
        if (list.size() == depth){
            list.add(node.val);
        }else if (node.val > list.get(depth)){
            list.set(depth, node.val);
        }
        max(node.left, ++depth, list);
        max(node.right, depth, list);
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
